Modern cryptography relies on the use of cryptographic algorithms, also known as ciphers, to encrypt data for secure transmission over networks such as the Internet. In addition to the primary function of preserving data confidentiality, cryptographic systems can serve a number of other functions, including preserving data integrity. This requires that the receiver of a message should be able to verify that the message has not been changed by a third party after encryption.
To avoid the need to keep cryptographic algorithms secret, which can be difficult when the algorithm is incorporated into commercially available products, present day algorithms use an encryption key K which can assume any one of a large number of possible values. The security of the encryption system then resides in the key, rather than in the details of the algorithm.
There are two general types of key-based algorithm, known as symmetric, or private-key, algorithms and asymmetric, or public-key algorithms. The present invention is concerned with symmetric algorithms. In most symmetric algorithm based encryption schemes, the encryption and decryption keys are the same and the sender and receiver must agree on a key before they can communicate securely. They must also ensure that the key remains secret, since the security of the system is compromised by a third party knowing the key.
FIG. 1 illustrates the basic principle of encrypted communication. Unencrypted data, known as plaintext P, is encrypted by the Sender using an encryption algorithm E and an encryption key K to produce encrypted data, known as ciphertext C. Mathematically, the operation can be written as EK(P)=C. The ciphertext is sent over a communication channel to a Receiver, where a decryption algorithm D is applied to recover the plaintext from the ciphertext. This operation can be written as DK(C)=P. The functions D and E have the property that DK(EK(P))=P, and D is referred to herein as the inverse of E. In the event that different, but cryptographically related, keys K1, K2 are used for encryption and decryption respectively, then the appropriate representations are Ek1(P)=C, DK2(C)=P and DK2(Ek1(P))=P.
Symmetric algorithms can be divided into two categories, generally referred to as block ciphers and stream ciphers. In general terms, stream ciphers operate on plaintext a single bit at a time and are considerably faster than block ciphers. For example, in a simple stream cipher, each bit of plaintext is exclusive or'd (XORed) with a respective bit from a pseudo-random stream of bits generated by a keystream generator.
Although a stream cipher provides the primary cryptographic function of preserving the confidentiality of a message, the preservation of data integrity requires an additional independent mechanism, since otherwise changes at one bit position in the plaintext result in changes at the corresponding position in the ciphertext. Therefore, additional circuits and/or memory may be required to implement an independent integrity preserving mechanism.
Block ciphers operate on groups of plaintext bits known as blocks. For example, a typical block size is 64 bits. Block ciphers are used because they are capable of providing both confidentiality and data integrity. However, they are in general considerably slower than stream ciphers. For example, the known DES block cipher encrypts data in 64-bit blocks, using a 56-bit key. This is used to generate a key schedule comprising 16 different 48-bit subsets of the key. All the outputs of the key schedule are used for the encryption of every plaintext block in a highly non-linear data randomising algorithm.
Reference is directed to Bruce Schneier, “Applied Cryptography”, Second Edition, Chapter 9, pp. 189–211, for an overview of block and stream ciphers and their modes of operation.